package com.algorithm;

/**
 * 比较含退格的字符串
 */
public class BackspaceStringCompare {

    public static boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1;
        int j = t.length() - 1;
        int sCount = 0;
        int tCount = 0;
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    sCount++;
                    i--;
                } else if (sCount > 0) {
                    sCount--;
                    i--;
                } else {
                    break;
                }
            }

            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    tCount++;
                    j--;
                } else if (tCount > 0) {
                    tCount--;
                    j--;
                } else {
                    break;
                }
            }
            if (i>=0&&j>=0){
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            }else {
                if (i>=0||j>=0){
                    return false;
                }
            }

            i--;
            j--;
        }
        return true;
    }

    public static void main(String[] args) {
//        String S = "ab#c";
//        String T = "ad#c";
//        System.out.println(backspaceCompare(S, T));
        String S = "ab##";
        String T = "c#d#";
        System.out.println(backspaceCompare(S, T));
    }
}
